package main

import (
	"fmt"
)

/**
执行用时：16 ms, 在所有 Go 提交中击败了63.08%的用户
内存消耗：5.3 MB, 在所有 Go 提交中击败了43.59%的用户
 */
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

	n := len(nums1) + len(nums2)
	if n % 2 == 1 {
		return get(nums1, nums2, n / 2 + 1)
	} else {
		return (get(nums1, nums2, n / 2) + get(nums1, nums2, n / 2 + 1)) / 2
	}
}

func get(nums1 []int, nums2 []int, k int) float64 {

	i, j := 0, 0
	for {
		if i == len(nums1) {
			return float64(nums2[j + k - 1])
		}
		if j == len(nums2) {
			return float64(nums1[i + k - 1])
		}
		if k == 1 {
			return float64(min(nums1[i], nums2[j]))
		}

		newI := min(i + k / 2, len(nums1)) - 1
		newJ := min(j + k / 2, len(nums2)) - 1
		if nums1[newI] <= nums2[newJ] {
			k -= newI - i + 1
			i = newI + 1
		} else {
			k -= newJ - j + 1
			j = newJ + 1
		}
	}
}

func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	nums1 := []int{1, 2}
	nums2 := []int{3, 4}
	fmt.Println(findMedianSortedArrays(nums1, nums2))
}
